class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

// 中序遍历：左子树 -> 根节点 -> 右子树

// 递归
function inorderTraversal(root: TreeNode | null): number[] {

    if (!root) return [];
    const result: number[] = [];
    if (root.left) {
        result.push(...inorderTraversal(root.left))
        return result;
    }
    if (root.val !== null) result.push(root.val)
    if (root.right) {
        result.push(...inorderTraversal(root.right))
    }

    return result;
};

// 迭代
function inorderTraversal1(root: TreeNode | null): number[] {

    if (!root) return [];
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let current: TreeNode | null = root;

    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop()||null;
        result.push(current!.val);
        current = current!.right;
    }

    return result;
};